\chapter{可分割验证码的识别}\label{chap:kefenge}

可分割验证码，是指那些字符位置固定，无变形，无扭曲，字符不相粘连的图形验证码，
随着图形分割算法和图像数字特征提取技术的繁荣发展，此类可分割验证码的安全性渐渐受到威胁，已经渐渐退出了历史舞台。
这里我们选择某教务系统的登录验证码作为识别对象（图\ref{fig:qzdl}），其字符清晰位置限定在某一区间，可以很好地将单个字符分割出来，逐一识别，具有很好的代表性。

\begin{figure}[!htbp]
  \centering
  \includegraphics[clip, width=0.20\textwidth]{qzdl}
  \bicaption{某教务系统的登录验证码}{Login verification code of a educational administration system}
  \label{fig:qzdl}
\end{figure}

\section{验证码图像预处理}

在正式开始识别验证码之前，我们通常要对验证码进行一些诸如灰化，去噪，二值化之类的图像预处理操作，
目的是突出验证码的主要特征，减弱噪点和干扰线对识别的干扰，使图形验证码的数字特征更加明显和有效。

\subsection{图像数字化}

首先我们需要读取一张图形验证码，我们知道图像的最小组成单元是像素，每个像素点都保存着图片在该像素点的RGB色值(取值范围0-255)，其中RGB分别代表红色（Red）、绿色（Green）和蓝色（Blue）。

\begin{definition}\label{def:img}
  假设图形验证码的宽为$width$像素，高为$height$像素，将图形验证码视作一个2维平面上的$width\times height$的矩阵$M _{width\times height}$。
  其上的每一点$m _{rgb}$代表一个像素，每个点（像素）是一个包含该点RGB色值的长度为3的数组。
\end{definition}

这样我们就成功地将一个图形验证码数字化为一个二维矩阵$M _{width\times height}$。

\subsection{灰化}

由定义\ref{def:img}我们可知此时的二维矩阵$M _{width\times height}$其实是一个“伪二维矩阵”，因为它在每个点还包含着RGB三个值，实际上是一个$width\times height\times 3$的三维数组。
对此我们可以继续给“伪二维矩阵”$M _{width\times height}$降维。
考虑到此图形验证码的不同颜色对验证码字符的人眼识别并无太大影响，说明我们即使丢掉了图像的颜色信息，而只保留其灰度信息也可以用肉眼正常识别此验证码。

\begin{figure}[!htbp]
  \centering
  \begin{subfigure}[b]{0.2\textwidth}
    \includegraphics[width=\textwidth]{yuan}
    \caption{}
  \end{subfigure}%
  ~~~~~~% add desired spacing
  \begin{subfigure}[b]{0.2\textwidth}
    \includegraphics[width=\textwidth]{quse}
    \caption{}
  \end{subfigure}
  \bicaption{图形验证码灰化前后对比图。(a) 灰化前，(b) 灰化后。}
  {Contrast before and after graying. (a) before,(b)after.}
\end{figure}

\begin{definition}\label{def:huihua}
  我们称使图形验证码失色而只保留其灰度信息的过程为验证码的灰化。\\
  灰化公式
  \begin{equation}
    \adddotsbeforeeqnnum%
    gray\left ( M _{width\times height} \right )=\left ( 0.299m _{r}+0.587m _{g}+0.114m _{b}  \right )_{width\times height}
  \end{equation}
\end{definition}

通过灰化变换$M _{width\times height}=gray\left ( M \right )$，得到了二维数值矩阵$M _{width\times height}$

\subsection{去噪}

观察到此图形验证码（图\ref{fig:qzdl}）字符周围有一些干扰线和噪点存在，这会对字符识别产生干扰，需要人为除去或削弱后再进行验证码识别。
通过查询相关资料，发现\citep{csdn2018gua}的验证码去噪点算法和去干扰项算法具有很好的实际效果，这里便是采取了他的去噪算法，对灰化后的图形验证码继续进行去噪处理。

\begin{figure}[h]
  \centering
  \begin{subfigure}[b]{0.2\textwidth}
    \includegraphics[width=\textwidth]{qian}
    \caption{}
  \end{subfigure}%
  ~~~~~% add desired spacing
  \begin{subfigure}[b]{0.2\textwidth}
    \includegraphics[width=\textwidth]{hou}
    \caption{}
  \end{subfigure}
  \\% line break
  \begin{subfigure}[b]{0.2\textwidth}
    \includegraphics[width=\textwidth]{yuan}
    \caption{}
  \end{subfigure}%
  ~~~~~% add desired spacing
  \begin{subfigure}[b]{0.2\textwidth}
    \includegraphics[width=\textwidth]{quzao}
    \caption{}
  \end{subfigure}
  \bicaption{图形验证码去噪前后对比图。(a) 去噪前，(b) 去噪后，(c) 去噪前，(d) 去噪后。}{Contrast before and after denoising. (a) before, (b)after, (c) before, (d) after.}
\end{figure}

\subsection{字符分割}
为了进一步降低验证码识别的难度，考虑将多个验证码字符切割成单个字符（\ref{fig:fenge}），再进行逐一识别。

\begin{figure}[h]
  \centering
  \begin{subfigure}[b]{0.2\textwidth}
    \includegraphics[width=\textwidth]{quzao}
    \caption{}
  \end{subfigure}
  \\
  \begin{subfigure}[b]{0.05\textwidth}
    \includegraphics[width=\textwidth]{1}
    \caption{}
  \end{subfigure}%
  ~~~~~~% add desired spacingj
  \begin{subfigure}[b]{0.05\textwidth}
    \includegraphics[width=\textwidth]{j}
    \caption{}
  \end{subfigure}
  ~~~~~~% add desired spacing
  \begin{subfigure}[b]{0.05\textwidth}
    \includegraphics[width=\textwidth]{p}
    \caption{}
  \end{subfigure}%
  ~~~~~~% add desired spacing
  \begin{subfigure}[b]{0.05\textwidth}
    \includegraphics[width=\textwidth]{h}
    \caption{}
  \end{subfigure}
  \bicaption{图形验证码单个字符的分割。(a) 原图，(b) 1，(c) j，(d) p，(e) h 。}{Division of graphic verification code.(a) origin, (b) 1, (c) j, (d) p, (e) h .}
  \label{fig:fenge}
\end{figure}

\subsection{二值化}

实际上将图形验证码灰化后我们发现此时的验证码背景大部分接近白色，而验证码字符接近于黑色，所以我们考虑将像素点灰度值进行二值化处理，进一步简化问题，突出图像的数字特征。

\begin{definition}\label{def:threshold}
  我们将图形验证码像素点灰度值大于等于数值$\theta$的视为1，其余像素点视为0，这里的$theta$称为图像二值化阈值。\\
  二值化公式
  \begin{equation}
    \adddotsbeforeeqnnum%
    threshold ( m )=\left\{\begin{matrix}
      1\; \; \; m\geqslant \theta
      \\ 
      0\;\; \; \; \; \;  else
    \end{matrix}\right.
  \end{equation}
\end{definition}

然后进行二值化变换$M _{width\times height}=threshold\left ( M \right )$转成0，1数值矩阵。

\section{验证码特征提取}

在进行完众多图像预处理步骤之后，开始提取验证码各个字符的数字特征。
首先，将100张图形验证码全部分割成单个字符，然后按照0-9，a-z的顺序新建36个文件夹，
将分割好的字符图像移动到对应的文件夹内分类整理好，并确保每个分类文件夹下面都有对应的字符文件。

然后，考虑如何提取字符数字特征。

一个最简单的方案就是直接将所有的字符图像二值化之后的0、1数值二维矩阵转成一维数组保存，这会保留原始字符图像的全部特征。
当然这其中也会有许多无用的特征，将全部数字特征保存虽然可行，但是显然会占用大量的存储空间和机器运行时间。
所以这里只抽取偶数行和偶数列的像素信息作为验证码字符的数字特征，这样可以直接使特征规模减少一半，而且实际上对识别结果也无明显影响。

\section{验证码的识别}

获取完所有验证码字符的数字特征之后，最后进行图形验证码的识别工作。
下面考虑怎样根据已有的验证码字符的数字特征确定未知的验证码字符。

\begin{definition}\label{def:xiangsidu}
  已知字符$x$的数字特征为$M_{x}$,未识别字符$y$的数字特征为$M_{y}$,则称数字特征$M_{x}$与$M_{y}$在相同位置数值相同的点的个数为两个字符之间的相似度。
  \begin{equation}
    XSD\left ( x,y \right )= \sum_{
    \begin{matrix}
    m_{xi}\in M_{x}
    \\ 
    m_{yi}\in M_{y}
    \end{matrix}}
    1-\left | m_{xi}-m_{yi} \right |
  \end{equation}
  记作$XSD(x,y)$。
\end{definition}

根据上面的定义可知，字符$x$与$y$的相似度$XSD(x,y)$越大，二者越相似。

考虑将未知字符$x$依次与0-9，a-z这36个字符的数字特征求相似度，可以认为得分最大者即为该字符图形的真实字符。
然后依次将分割好的4个字符进行特征识别得到4个预测字符，之后将所得字符按顺序拼接起来即为最终的图形验证码识别结果。

\section{识别结果}

经过检验，该方法在100个未知图形验证码的数据集中达到了100\%的准确率！让人忍不住感叹，大道至简。

数学之美，就在于它可以将现实生活中看似很复杂的问题，不断抽象出更深层次的结构和内涵，不断简化问题，最终归于至简的真理。